// TheNumberOfOne.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <time.h>

clock_t BeginTimer(){
	//timer declaration
	clock_t Begin;
	Begin = clock() * CLK_TCK;
	return Begin;
}

clock_t EndTimer(clock_t begin){
	//timer declaration
	clock_t End;
	End = clock() * CLK_TCK;   //stop the timer
	return End;
}
/*
long Count1InAInterger(long n){
	long iNum = 0;
	while(n != 0){
		iNum += (n%10==1)?1:0;
		n /= 10;
	}
	return iNum;
}

long f(long n){
	long iCount = 0;
	for(long i=0;i <=n;i++){
		iCount += Count1InAInterger(i);
	}
	return iCount;
}
*/


long Sum1s(long n){
	long iCount = 0;
	long iFactor = 1;
	long iLowerNum = 0;
	long iCurrNum = 0;
	long iHigherNum = 0;

	while(n/iFactor != 0){
		iLowerNum = n -(n/iFactor)*iFactor;
		iCurrNum = (n/iFactor)%10;
		iHigherNum = n/(iFactor * 10);
		switch(iCurrNum){
			case 0:
				iCount += iHigherNum * iFactor;
				break;
			case 1:
				iCount += iHigherNum * iFactor + iLowerNum + 1;
				break;
			default:
				iCount += (iHigherNum +1)*iFactor;
				break;
		}
		iFactor *= 10;
	}

	return iCount;
}

int _tmain(int argc, _TCHAR* argv[])
{
	double begin = BeginTimer();
	unsigned long highMargin = 4294967295,factor = 1000000000,tmpResult = 0 ,maxN =0 ;
	// variable declarations used for time calculation
	float elapTicks;
	float elapMilli;

	printf ("Timer set to: %.2f\n", begin); // print the initialised timer (0)

	long re = Sum1s(1111111111);

	while(factor > 0){
		tmpResult = Sum1s(highMargin);
		if(tmpResult > highMargin){
			highMargin -= factor;
		}else if(tmpResult < highMargin){
			highMargin += factor;
			if(factor >= 10){
				factor /= 10;
			}
		}else{
			maxN = highMargin;
			break;
		}
	}



	elapTicks = EndTimer(begin);    // stop the timer, and calculete the time taken
	printf("The Number of 1s: %d\n",re);
	printf("The max number that f(n)==n is: %d\n",maxN);
	

	// variable definitions on to calculate time taken
	
	elapMilli = elapTicks/1000;     // milliseconds from Begin to End
	printf ("Milliseconds passed: %.2f\n", elapMilli);

	char c;
	scanf("%c",&c);
	return 0;
}

